package com.leetcode;

/**
 * 106.从中序和后序遍历中构建二叉树
 *
 * @author wangruiyang <wangruiyang@kuaishou.com>
 * Created on 2024-02-21
 */
public class No106 {
    @SuppressWarnings("checkstyle:VisibilityModifier")
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }


    public static TreeNode buildTree(int[] inorder, int inOrderStart, int inOrderEnd, int[] postorder, int postStart,
            int postEnd) {
        if (inOrderStart > inOrderEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        int temp = 0;
        for (int i = inOrderStart; i <= inOrderEnd; i++) {
            if (inorder[i] == postorder[postEnd]) {
                temp = i;
                break;
            }
        }
        root.left =
                buildTree(inorder, inOrderStart, temp - 1, postorder, postStart, postStart + (temp - inOrderStart) - 1);
        root.right = buildTree(inorder, temp + 1, inOrderEnd, postorder, postStart + (temp - inOrderStart), postEnd - 1);
        return root;
    }


    public static void main(String[] args) {
        int[] inorder = new int[] { 9, 3, 15, 20, 7};
        int[] postorder = new int[] {9, 15, 7, 20, 3};
        buildTree(inorder, postorder);
    }
}
